Networks are the principal means for communicating multimedia between communication devices. The content of the multimedia can include data, audio, text, images, video, etc. Communication devices include input/output devices, computers, terminals, multimedia workstations, fax machines, printers, servers, telephones, and personal digital assistants.
A multimedia network typically includes network switches connected to each other and to the communication devices by circuits. The circuits can be physical or virtual. In the latter case, the circuit is specified by a source and destination address. The actual physical circuit used will vary over time, depending on network traffic and resource requirements and availability, such as bandwidth.
The multimedia can be formatted in many forms, but increasingly it is formatted into packets. Packets in transit between the communication devices may temporarily be stored in buffers at the switches along the path of the circuit pending sufficient available bandwidth on subsequent circuits along the path.
Important considerations in network operation are admission control and resource allocation. Typically, admission control and resource allocation are ongoing processes that are performed periodically during transmission of bit streams. The admission control and resource allocation determinations may take into account various factors such as network topology and current available network resources, such as buffer space in the switches and capacity in the circuits, any quality-of-service commitments (QoS), e.g., guaranteed bandwidth, and delay or packet loss probabilities.
The admission control and resource allocation problem is complicated when a variable bit-rate (VBR) multimedia source or communications device seeks access to the network and requests a virtual circuit for streaming data. The complication arises because the features, which describe the variations in content of the multimedia, are often imprecise. Thus, it is difficult to predict what the requirements for network resources, such as requirements for bandwidth, by the VBR source will be in the future. For example, the bandwidth requirements of VBR sources typically vary with time, and the bandwidth variations typically are difficult to characterize. Thus, the admission-allocation determination is made with information that may not accurately reflect the demands that the VBR source may place on the network, thereby causing degraded network performance.
More particularly, if the network resource requirements are overestimated, then the network will run under capacity. Alternatively, if the network resources requirements are underestimated, then the network may become congested and packets traversing the network may be lost, see, e.g., Roberts, “Variable-Bit-Rate Traffic-Control in B-ISDN,” IEEE Comm. Mag., pp. 50-56, September 1991; Elwalid et al, “Effective Bandwidth of General Markovian Traffic Sources and Admission Control of High Speed Networks,” IEEE/ACM Trans. on Networking, Vol. 1, No. 3, pp. 329-343, 1993. Guerin et al., “Equivalent Capacity and its Application to Bandwidth Allocation in High-Speed Networks,” IEEE J. Sel. Areas in Comm., Vol. 9, No. 7, pp. 968-981, September 1991.
Transmission of digital multimedia over bandwidth-limited networks will become increasingly important in future Internet and wireless communication. It is a challenging problem to cope with ever changing network parameters, such as the number of multimedia sources and receivers, the bandwidth required by each stream, and the topology of the network itself. Optimal resource allocation should dynamically consider global strategies, i.e., global network management, as well as local strategies, such as, admission control during individual connections.
Bandwidth allocation and management for individual bit streams is generally done at the “edges” of the network in order to conserve computational resources of the network switches. While off-line systems can determine the exact bandwidth characteristics of a stream in advance, in many applications, on-line processing is desired or even required to keep delay and computational requirements low. Furthermore, any information used to make bandwidth decisions should be directly available in the compressed bit stream. It is desirable to have a resource management system that can accurately estimate the required bandwidth in real-time using only compressed domain information.
Resource Renegotiating for VBR Video
Of all multimedia, it is particularly desired to improve resource allocation for VBR video and audio data. These are becoming increasingly popular due to their consistent visual and acoustic quality. The hallmark of VBR data is that bandwidth undergoes both short-term and long-term changes, in reaction to the complexity and therefore, compressibility of the underlying content. Moreover, the long-term variations are more difficult to handle and being able to predict the estimated bandwidth over longer intervals is desired.
As stated above, allocating a constant amount of bandwidth to a VBR stream will usually yield one or more results: inefficient use of network resources, due to over or under-allocated bandwidths, and a requirement of large network buffers and consequent delay. Therefore, the bandwidth requests made by the VBR source should be periodically renegotiated in order to obtain high network utilization and low delay. Determining appropriate renegotiation points is also a problem. If renegotiation is too frequent, overhead increases. On the other hand, if the renegotiation is infrequent, coarse estimations are made.
Conventional methods typically renegotiate resources according to changes in bit stream level statistics, see Zhang et al., “RED-VBR: A new approach to support delay-sensitive VBR video in packet-switched networks,” Proc. NOSSDAV, pp. 258-272 1995. The relationship between past and future traffic is parametrically modeled in techniques described by Chong et al, “Predictive dynamic bandwidth allocation for efficient transport of real-time VBR video over ATM,” IEEE J. Sel. Areas of Comm., Vol. 13, No. 1, pp. 12-23, 1995, and Izquierdo et al. “A survey of statistical source models for variable bit-rate compressed video,” Multi-media Systems, Vol. 7, No. 3, pp. 199-213, 1999, and references therein.
Content-based methods are motivated by the high correlation between long-term traffic characteristics and video content, see Dawood et al, “MPEG video modeling based on scene description,” Proc. IEEE ICIP, Vol. 2, pp. 351-355, 1998, and Bocheck et al, “Content-based VBR traffic modeling and its application to dynamic network resource allocation,” Research Report 48c-98-20, Columbia Univ., 1998. Although multimedia content is a major factor in determining the bandwidth allocation, content alone may not be sufficient for predicting future traffic and in estimating how much resource to request.
Bandwidth Renegotiation Points
In the prior art, on-line determination of bandwidth renegotiation points for VBR content generally falls into three categories: deterministic, traffic-based, and content-based.
Deterministically setting the renegotiation points is the simplest method. Bandwidth requests are made every n frames, where n is an empirically determined balance between request overhead and correlation of bit-rates.
Traffic-based renegotiation occurs when a stream exceeds a previously negotiated bandwidth request, or when utilization drops below some threshold level. Although traffic-based renegotiation tracks the real bandwidth more closely, a single complex frame in a video can cause the requested bandwidth to remain unnecessarily elevated for some time.
A more “natural” renegotiation point is content-based, for example, a scene or “shot” boundary. A shot is defined as all frames acquired in a continuous sequence between when the camera's shutter opens and closes. By examining the bits used per frame in the VBR video, one can learn that the most dramatic change in bit usage occurs at the beginning of a new segment. Within a single segment, the traffic characteristics are usually relatively constant. If a segment has a sudden change in content features, the change can be considered another segment boundary, as far as renegotiation is concerned.
Many methods are known for finding segment boundaries in the compressed domain, see, for example, Yeo et al, “Rapid scene analysis on compressed video,” IEEE Tr. Circuits and Systems for Video Tech., vol. 5, No. 6, pp. 533-544, 1995. That method uses a windowed relative threshold on the sum of absolute pixel differences, and allows for fast, on-line determination of renegotiation points.
Bandwidth Request Per Interval
The next step is to determine how much resource to request at each renegotiation point, without introducing significant delay. For natural renegotiation points such as segment boundaries, previous traffic cannot generally help to determine how much resource to request when the traffic pattern has changed. With the requirement of on-line processing in mind, one can predict the traffic for the entire segment based on a short observation of the beginning part of a new segment, as illustrated in FIG. 1.
In FIG. 1, a video source 101 has segment boundaries 102, and observation periods 103. Bandwidth renegotiation points 104 occur after the observation periods 103. The video 101 is transmitted using the newly allocated bandwidth if the resources are granted at 105. The observation periods will inevitably introduce a short delay in renegotiation. The video can be transmitted without delay 110. With this approach, over-requested traffic may occur during time intervals t 111. A network buffer can smooth this traffic out if t is small. For applications tolerating a short-delay, the video 120 may be transmitted with t-second delay 121 so that the video traffic is within the bounds of the negotiated agreement.
The content-based prediction method described by Bocheck et al. includes training and testing stages. In the training stage, content features of a training video are quantized into a small number of levels, e.g., slow, medium, or fast motion. Every possible combination of significant features is labeled as a content class for which a typical traffic pattern is determined. During testing, the content class of each segment in the video is identified by extracting the same features, and the typical traffic pattern of the class is used as the predicted traffic for that segment.
However, the Bocheck method has some potential weaknesses. First, the specific prediction structure, via classification, can only feasibly incorporate a limited number of coarsely quantized features; each feature is weighted equally, rather than by its relevance to traffic. Second, prediction based solely on content may not be applicable for bit streams produced with different encoding algorithms or parameters. Third, not all available information during the observation periods is used at the renegotiation points.
Inaccurate predictions can cause allocation requests not to be granted or insufficient resources to be requested. This may result in denial of service, dropped packets, or transcoding to a lower bit-rate, perhaps with degraded quality.
Therefore, there is a need for an improved method and system for dynamically allocating network resources at renegotiation points while transferring multimedia content over a network.